package com.leetcode.partition7;

import java.util.HashMap;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2021/10/6 9:40
 */
public class LC695岛屿的最大面积 {

    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static int maxAreaOfIsland(int[][] grid) {
        return unionFind(grid);
    }

    public static void main(String[] args) {
        int[][] grid = {
                {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}
        };
//        int[][] grid = {
//                {0, 1, 0, 0, 1},
//                {1, 1, 0, 1, 0},
//                {0, 1, 0, 1, 1}
//        };
        System.out.println(maxAreaOfIsland(grid));
    }

    private static int unionFind(int[][] grid) {
        //保存以key为根结点的岛屿的面积为value
        Map<Integer, Integer> areaMap = new HashMap<>();
        int answer = 0;
        int[] ancestor = new int[grid.length * grid[0].length];
        //二维数组映射成一维数组
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) continue;
                int index = i * grid[0].length + j;
                ancestor[index] = index;
            }
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) continue;
                for (int[] dir : dirs) {
                    int rowIndex = i + dir[0], colIndex = j + dir[1];
                    //凡是当前坐标的邻坐标越界或者邻坐标为'0'，都视为无效，否则，将邻坐标合并到当前坐标中
                    if (rowIndex < 0 || rowIndex >= grid.length || colIndex < 0 || colIndex >= grid[0].length || grid[rowIndex][colIndex] == 0) {
                        continue;
                    }
                    int neighborIndex = rowIndex * grid[0].length + colIndex;
                    union(ancestor, i * grid[0].length + j, neighborIndex);
                }
            }
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) continue;
                //找到当前的根节点，并将其面积加1
                int ancestorIndex = find(ancestor, i * grid[0].length + j);
                areaMap.put(ancestorIndex, areaMap.getOrDefault(ancestorIndex, 0) + 1);
                answer = Math.max(answer, areaMap.get(ancestorIndex));
            }
        }
        return answer;
    }

    private static int find(int[] ancestor, int x) {
        if (x == ancestor[x]) return x;
        return find(ancestor, ancestor[x]);
    }

    private static void union(int[] ancestor, int x, int y) {
        int parentX = find(ancestor, x), parentY = find(ancestor, y);
        if (parentX != parentY) ancestor[parentY] = parentX;
    }
}
